<!DOCTYPE html>
<html lang="en">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Auto-vectorization in GCC</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
    <h1>Auto-vectorization in GCC<br /></h1>

    <p>The goal of this project was to develop a loop and basic block
    vectorizer in GCC, based on the <a href="./">tree-ssa</a> framework.
    It has been completed and the functionality has been part of GCC
    for years.</p>

    <h2>Table of Contents</h2>

    <ul>
        <li><a href="#news">Latest News</a></li>

        <li><a href="#vec_todo">Contributing</a></li>

        <li><a href="#using">Using the Vectorizer</a></li>

        <li><a href="#vectorizab">Vectorizable Loops</a></li>

        <li><a href="#unvectoriz">Unvectorizable Loops</a></li>

        <li><a href="#oldnews">Previous News and Status</a></li>

        <li><a href="#References">References/Documentation</a></li>

        <li><a href="#high-level">High-Level Plan of
        Implementation</a></li>
    </ul>

    <h2 id="news">Latest News</h2>
<dl>
  <dt>2011-10-23</dt>
     <dd>
     <ol>
        <li>Vectorization of reduction in loop SLP.
            Both <a href="#slp-reduc-2"> multiple reduction cycles</a> and 
            <a href="#slp-reduc-1"> reduction chains</a> are supported. </li>
        <li>Various <a href="#slp"> basic block vectorization (SLP)</a>
            improvements, such as
            better data dependence analysis, support of misaligned accesses
            and multiple types, cost model.</li>
        <li>Detection of vector size:
            <a href= "https://gcc.gnu.org/ml/gcc-patches/2010-10/msg00441.html">
            https://gcc.gnu.org/ml/gcc-patches/2010-10/msg00441.html</a>.</li>
        <li>Vectorization of loads with <a href="#negative"> negative step</a>.</li>
        <li>Improved realignment scheme: 
            <a href= "https://gcc.gnu.org/ml/gcc-patches/2010-06/msg02301.html">
            https://gcc.gnu.org/ml/gcc-patches/2010-06/msg02301.html</a>.</li>
        <li>A new built-in, <a href="#assume-aligned">
            <code>__builtin_assume_aligned</code></a>, has been added,
            through which the compiler can be hinted about pointer alignment.</li>
        <li>Support of <a href="#strided"> strided accesses</a> using
            memory instructions that have
            the interleaving "built in", such as NEON's vldN and vstN.</li>
        <li>The vectorizer now attempts to reduce over-promotion of operands in some vector
            operations: <a href= "https://gcc.gnu.org/ml/gcc-patches/2011-07/msg01472.html">
            https://gcc.gnu.org/ml/gcc-patches/2011-07/msg01472.html</a>.</li>
        <li><a href="#widen-shift"> Widening shifts</a> are now detected and vectorized
            if supported by the target.</li>
        <li>Vectorization of conditions with <a href="#cond-mix"> mixed types</a>.</li>
        <li>Support of loops with <a href="#bool"> bool</a>.</li>
    </ol>
    </dd>
</dl>

<dl>
  <dt>2009-12-03</dt>
     <dd>The following new vectorization features were committed to mainline:
     <ol>
        <li>vectorization of <a href="#nested"> conditions in nested loop</a> (2009-07-20)</li>
        <li>vectorization of <a href="#double"> double reduction</a> (reductions carried 
            by two nested loops) (2009-07-12)</li>
        <li>vectorization of <a href="#nested">  nested cycles</a> (dependence cycles
            other than reduction cycles in nested loops) (2009-06-16)</li>
        <li>support of misaligned stores for platforms that allow misaligned 
            access (2009-06-05)</li>
        <li><a href="#bb-slp">basic block SLP</a>  (vectorization of straight line 
            code) (2009-05-25)</li>
        <li>avoid versioning of vectorized loop if possible (2009-04-02)
            <a href= "https://gcc.gnu.org/ml/gcc-patches/2009-03/msg01784.html">
            (https://gcc.gnu.org/ml/gcc-patches/2009-03/msg01784.html)</a>.</li>
        <li>support <a href="#slp-perm">load permutations</a> in loop-aware 
            SLP (2008-08-25)</li>
        <li>support multiple types in loop-aware SLP (2008-08-19)</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2008-08-11</dt>
    <dd>
    <ol>
      <li>Vectorization supports integer type conversions also when one type is more
          than two times bigger than the other (e.g. char to int) (2008-08-11).</li>
      <li><code>UNITS_PER_SIMD_WORD</code> can be different for different scalar 
          types (2008-05-22).</li>
      <li>Vector shifts by a vector shift amount differentiated from vector
          shifts with scalar shift amount (2008-05-14).</li>
      <li>Complete unrolling enabled before vectorization, relying on 
	  intra-iteration vectorization (aka SLP) to vectorize unrolled loops (2008-04-27).</li>
      <li>Further refinements to the cost model (2007-12-06).</li>
      <li><code>-ftree-vectorize</code> is turned on under <code>-O3</code>
	(2007-09-18).</li>
    </ol>
    </dd>
</dl>


    <h2 id="vec_todo">Contributing</h2>

    <p>This project was started by Dorit (Naishlos) Nuzman. Current contributors 
    to this project include Revital Eres, Richard Guenther, Jakub Jelinek, Michael Matz,
    Richard Sandiford, and Ira Rosen.
    This web page
    is maintained by <a href="mailto:irar@il.ibm.com">Ira Rosen &lt;irar@il.ibm.com&gt;</a>.
    For a list of missing features and possible enhancements see 
    <a href= "https://gcc.gnu.org/wiki/VectorizationTasks">
	      https://gcc.gnu.org/wiki/VectorizationTasks</a>.
    </p>

    <h2 id="using">Using the Vectorizer</h2>

    <p>Vectorization is enabled by the flag
    <code>-ftree-vectorize</code> and by default
    at <code>-O3</code>. To allow vectorization on
    powerpc* platforms also use <code>-maltivec</code>. On i?86 and
    x86_64 platforms use <code>-msse/-msse2</code>. To enable vectorization
    of floating point reductions use <code>-ffast-math</code> or 
    <code>-fassociative-math</code>.</p>

    <p>The vectorizer
    test cases demonstrate the current vectorization capabilities;
    these can be found under
    gcc/gcc/testsuite/gcc.dg/vect/. Information on which
    loops were or were not vectorized and why, can be obtained
    using the flag <code>-ftree-vectorizer-verbose</code>. For details
    see <a href=
            "https://gcc.gnu.org/ml/gcc-patches/2005-01/msg01247.html">
            https://gcc.gnu.org/ml/gcc-patches/2005-01/msg01247.html</a>.
    Example output using <code>-ftree-vectorizer-verbose=2</code>:</p>

<pre>
vect-1.c:82: note: not vectorized, possible dependence between data-refs a[i_124] and a[i_83]
vect-1.c:72: note: LOOP VECTORIZED.
vect-1.c:64: note: LOOP VECTORIZED.
vect-1.c:56: note: LOOP VECTORIZED.
vect-1.c:49: note: LOOP VECTORIZED.
vect-1.c:41: note: not vectorized: unsupported use in stmt.
vect-1.c:31: note: not vectorized: unsupported use in stmt.
vect-1.c:13: note: vectorized 4 loops in function.
</pre>

    <p>Basic block vectorization, aka SLP, is enabled by the flag 
    <code>-ftree-slp-vectorize</code>, and requires the same platform dependent flags 
    as loop vectorization. Basic block SLP is enabled by default at <code>-O3</code>
    and when <code>-ftree-vectorize</code> is enabled.</p> 

    <h2 id="vectorizab">Vectorizable Loops</h2>

    <p>"feature" indicates
    the vectorization capabilities demonstrated by the
    example.</p>
    
<strong id="example1">Example 1:</strong>

<pre>
int a[256], b[256], c[256];
foo () {
  int i;

  for (i=0; i&lt;256; i++){
    a[i] = b[i] + c[i];
  }
}
</pre>

<strong id="example2">Example 2:</strong>

<pre>
int a[256], b[256], c[256];
foo (int n, int x) {
   int i;

   /* feature: support for unknown loop bound  */
   /* feature: support for loop invariants  */
   for (i=0; i&lt;n; i++)
      b[i] = x;
   }

   /* feature: general loop exit condition  */
   /* feature: support for bitwise operations  */
   while (n--){
      a[i] = b[i]&amp;c[i]; i++;
   }
}
</pre>

<strong id="example3">Example 3:</strong>

<pre>
typedef int aint __attribute__ ((__aligned__(16)));
foo (int n, aint * __restrict__ p, aint * __restrict q) {

   /* feature: support for (aligned) pointer accesses.  */
   while (n--){
      *p++ = *q++;
   }
}
</pre>

<strong id="example4">Example 4:</strong>

<pre>
typedef int aint __attribute__ ((__aligned__(16)));
int a[256], b[256], c[256];
foo (int n, aint * __restrict__ p, aint * __restrict__ q) {
   int i;

   /* feature: support for (aligned) pointer accesses  */
   /* feature: support for constants  */
   while (n--){
      *p++ = *q++ + 5;
   }

   /* feature: support for read accesses with a compile time known misalignment  */
   for (i=0; i&lt;n; i++){
      a[i] = b[i+1] + c[i+3];
   }

   /* feature: support for if-conversion  */
   for (i=0; i&lt;n; i++){
      j = a[i];
      b[i] = (j &gt; MAX ? MAX : 0);
   }
}
</pre>

<strong id="example5">Example 5:</strong>

<pre>
struct a {
  int ca[N];
} s;
for (i = 0; i &lt; N; i++)
  {
    /* feature: support for alignable struct access  */
    s.ca[i] = 5;
  }
</pre>

<strong id="example6">Example 6:</strong> gfortran:

<pre>
DIMENSION A(1000000), B(1000000), C(1000000)
READ*, X, Y
A = LOG(X); B = LOG(Y); C = A + B
PRINT*, C(500000)
END
</pre>

<strong id="example7">Example 7:</strong>

<pre>
int a[256], b[256];
foo (int x) {
   int i;

   /* feature: support for read accesses with an unknown misalignment  */
   for (i=0; i&lt;N; i++){
      a[i] = b[i+x];
   }
}
</pre>

<strong id="example8">Example 8:</strong>
    
<pre>
int a[M][N];
foo (int x) {
   int i,j;

   /* feature: support for multidimensional arrays  */
   for (i=0; i&lt;M; i++) {
     for (j=0; j&lt;N; j++) {
       a[i][j] = x;
     }
   }
}
</pre>

<strong id="example9">Example 9:</strong>

<pre>
unsigned int ub[N], uc[N];
foo () {
  int i;

  /* feature: support summation reduction.
     note: in case of floats use -funsafe-math-optimizations  */
  unsigned int diff = 0;
  for (i = 0; i &lt; N; i++) {
    udiff += (ub[i] - uc[i]);
  }
</pre>

<strong>Example 10:</strong>

<pre>
/* feature: support data-types of different sizes.
   Currently only a single vector-size per target is supported; 
   it can accommodate n elements such that n = vector-size/element-size 
   (e.g, 4 ints, 8 shorts, or 16 chars for a vector of size 16 bytes). 
   A combination of data-types of different sizes in the same loop 
   requires special handling. This support is now present in mainline,
   and also includes support for type conversions.  */

short *sa, *sb, *sc;
int *ia, *ib, *ic;
for (i = 0; i &lt; N; i++) {
  ia[i] = ib[i] + ic[i];
  sa[i] = sb[i] + sc[i];
}

for (i = 0; i &lt; N; i++) {
  ia[i] = (int) sb[i];
}
</pre>

<strong id="strided">Example 11:</strong>

<pre>
/* feature: support strided accesses - the data elements
   that are to be operated upon in parallel are not consecutive - they
   are accessed with a stride &gt; 1 (in the example, the stride is 2):  */

for (i = 0; i &lt; N/2; i++){
  a[i] = b[2*i+1] * c[2*i+1] - b[2*i] * c[2*i];
  d[i] = b[2*i] * c[2*i+1] + b[2*i+1] * c[2*i];
}
</pre>

<strong id="induction">Example 12:</strong> Induction:

<pre>
for (i = 0; i &lt; N; i++) {
  a[i] = i;
}
</pre>

<strong id="outer">Example 13:</strong> Outer-loop:

<pre>
  for (i = 0; i &lt; M; i++) {
    diff = 0;
    for (j = 0; j &lt; N; j+=8) {
      diff += (a[i][j] - b[i][j]);
    }
    out[i] = diff;
  }
}
</pre>

<strong id="double">Example 14:</strong> Double reduction:

<pre>
  for (k = 0; k &lt; K; k++) {
    sum = 0;
    for (j = 0; j &lt; M; j++)
      for (i = 0; i &lt; N; i++)
          sum += in[i+k][j] * coeff[i][j];

    out[k] = sum;
  }
</pre>

<strong id="nested">Example 15:</strong> Condition in nested loop:

<pre>
  for (j = 0; j &lt; M; j++)
    {
      x = x_in[j];
      curr_a = a[0];

      for (i = 0; i &lt; N; i++)
        {
          next_a = a[i+1];
          curr_a = x &gt; c[i] ? curr_a : next_a;
        }

      x_out[j] = curr_a;
    }
</pre>

<strong id="slp-perm">Example 16:</strong> Load permutation in loop-aware SLP:

<pre>
  for (i = 0; i &lt; N; i++)
    {
       a = *pInput++;
       b = *pInput++;
       c = *pInput++;

       *pOutput++ = M00 * a + M01 * b + M02 * c;
       *pOutput++ = M10 * a + M11 * b + M12 * c;
       *pOutput++ = M20 * a + M21 * b + M22 * c;
    }
</pre>

<strong id="bb-slp">Example 17:</strong> Basic block SLP:

<pre>
void foo ()
{
  unsigned int *pin = &amp;in[0];
  unsigned int *pout = &amp;out[0];

  *pout++ = *pin++;
  *pout++ = *pin++;
  *pout++ = *pin++;
  *pout++ = *pin++;
}
</pre>

<strong id="slp-reduc-2">Example 18:</strong> Simple reduction in SLP:

<pre>
int sum1;
int sum2;
int a[128];
void foo (void)
{
  int i;

  for (i = 0; i &lt; 64; i++)
    {
      sum1 += a[2*i];
      sum2 += a[2*i+1];
    }
}
</pre>

<strong id="slp-reduc-1">Example 19:</strong> Reduction chain in SLP:

<pre>
int sum;
int a[128];
void foo (void)
{
  int i;

  for (i = 0; i &lt; 64; i++)
    {
      sum += a[2*i];
      sum += a[2*i+1];
    }
}
</pre>

<strong id="slp">Example 20:</strong> Basic block SLP with
multiple types, loads with different offsets, misaligned load,
and not-affine accesses:

<pre>
void foo (int * __restrict__ dst, short * __restrict__ src,
          int h, int stride, short A, short B)
{
  int i;
  for (i = 0; i &lt; h; i++)
    {
      dst[0] += A*src[0] + B*src[1];
      dst[1] += A*src[1] + B*src[2];
      dst[2] += A*src[2] + B*src[3];
      dst[3] += A*src[3] + B*src[4];
      dst[4] += A*src[4] + B*src[5];
      dst[5] += A*src[5] + B*src[6];
      dst[6] += A*src[6] + B*src[7];
      dst[7] += A*src[7] + B*src[8];
      dst += stride;
      src += stride;
    }
}
</pre>

<strong id="negative">Example 21:</strong> Backward access:

<pre>
int foo (int *b, int n)
{
  int i, a = 0;

  for (i = n-1; i &ge; 0; i--)
    a += b[i];

  return a;
}
</pre>

<strong id="assume-aligned">Example 22:</strong> Alignment hints:

<pre>
void foo (int *out1, int *in1, int *in2, int n)
{
  int i;

  out1 = __builtin_assume_aligned (out1, 32, 16);
  in1 = __builtin_assume_aligned (in1, 32, 16);
  in2 = __builtin_assume_aligned (in2, 32, 0);

  for (i = 0; i &lt; n; i++)
    out1[i] = in1[i] * in2[i];
}
</pre>

<strong id="widen-shift">Example 23:</strong> Widening shift:

<pre>
void foo (unsigned short *src, unsigned int *dst)
{
  int i;

  for (i = 0; i &lt; 256; i++)
    *dst++ = *src++ &lt;&lt; 7;
}
</pre>

<strong id="cond-mix">Example 24:</strong> Condition with mixed types:

<pre>
#define N 1024
float a[N], b[N];
int c[N];

void foo (short x, short y)
{
  int i;
  for (i = 0; i &lt; N; i++)
    c[i] = a[i] &lt; b[i] ? x : y;
}
</pre>

<strong id="bool">Example 25:</strong> Loop with bool:

<pre>
#define N 1024
float a[N], b[N], c[N], d[N];
int j[N];

void foo (void)
{
  int i;
  _Bool x, y;
  for (i = 0; i &lt; N; i++)
    {
      x = (a[i] &lt; b[i]);
      y = (c[i] &lt; d[i]);
      j[i] = x &amp; y;
    }
}
</pre>

    <h2 id="unvectoriz">Unvectorizable Loops</h2>

    <p>Examples of loops that currently cannot be
    vectorized:</p>
    
<strong>Example 1:</strong> Uncountable loop:
    
<pre>
while (*p != NULL) {
  *q++ = *p++;
}
</pre>

    <p> Also see  <a href= "https://gcc.gnu.org/wiki/VectorizationTasks">
              https://gcc.gnu.org/wiki/VectorizationTasks</a> 
    and a list of vectorizer missed-optimization PRs in the GCC bug tracker.</p>

    <h2 id="oldnews">Previous News and Status</h2>

<dl>
  <dt>2007-09-17</dt>
    <dd>
    <ol>
      <li><code>-ftree-vectorize</code> is going to be turned on under
        <code>-O3</code>.</li>
      <li>Cost-model tweaks and x86_64 specific costs committed to mainline
        (2007-09-10).</li>
      <li>Vectorization that exploits intra-iteration parallelism (ala SLP)
        was committed to mainline (2007-09-09).</li>
      <li><code>-fassociative-math</code> can be used instead of
        <code>-ffast-math</code> to enable vectorization of reductions of
        floats (2007-09-04).</li>
      <li>Initial support for vectorization of outer-loops (doubly nested
        loops) was committed to mainline (2007-08-19).</li>
      <li>Run-time dependence testing using loop-versioning was committed
        to mainline (2007-08-16).</li>
    </ol>
    </dd>
</dl>

<dl>
  <dt>2007-07-25</dt>
     <dd>The new vectorization feature that exploits intra-iteration parallelism
         (to be submitted to GCC 4.3) was presented at the GCC summit last week ("Loop-aware SLP").
         Also at the summit, we held a BOF on vectorization and other loop optimizations. The summary
         of the BOF can be found here: <a href="https://gcc.gnu.org/wiki/LoopOptimizationsBOF">
         https://gcc.gnu.org/wiki/LoopOptimizationsBOF</a>. Following the BOF the vectorizer's todo list
         was also updated (<a href="https://gcc.gnu.org/wiki/VectorizationTasks">
         https://gcc.gnu.org/wiki/VectorizationTasks</a>).
     </dd>
     <dd>Mainline updates:
     <ol>
        <li>SPU specific costs for the cost model committed to mainline (2007-07-12).
            Tuning for other platforms (PPC, x86) ongoing.</li>
        <li>Initial cost model implementation committed to mainline
            (2007-06-08).</li>
        <li>Vectorization of fp/integer conversions of different sizes (e.g. float/short)
            committed to mainline (2007-05-17).</li>
        <li>Data-refs analysis was rewritten and improved (2007-05-13).</li>
     </ol>
     </dd>
     <dd>Autovect-branch updates:
     <ol>
        <li>Outer-loop vectorization was enhanced to support aligned and unaligned
            memory references in the inner-loop, using the optimized realignment
            scheme when possible.</li>
        <li>Vectorization that exploits intra-iteration parallelism (ala SLP)
            was added to the vectorizer (that so far exploited only inter-iteration
            parallelism).</li>
        <li>The vectorizer cost model was extended to support the above two new vectorization
            features (outer-loop and "SLP").</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2007-05-09</dt>
     <dd>
     <ol>
        <li>Vectorization of fp/integer conversions of different sizes (e.g. float/short)
            is soon to be committed to mainline.</li>
        <li>Initial cost model implementation is soon to be committed to
            mainline.</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2007-04-22</dt>
     <dd>
     <ol>
        <li>Vectorization of float/double conversions was added to mainline.</li>
        <li>Initial vectorization support for certain forms of outer-loops (doubly
            nested loops) was added to autovect-branch. </li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2007-02-21</dt>
     <dd>
     <ol>
        <li>Vectorization of float/int conversions added to mainline.</li>
        <li>Vectorization of inductions added to mainline.</li>
        <li>Vectorization of function-calls added to mainline.</li>
        <li>Improvements to vectorization of strided-accesses - added to autovect-branch.</li>
        <li>Discussion on building a cost-model for the vectorizer - started on the mailing list.</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2007-01-14</dt>
     <dd>
     <ol>
        <li>A new flag to limit vectorization to loops with large enough loop-bound was
            added: <code>--param min-vect-loop-bound=X</code> prevents
            vectorization of loops whose vectorized loop-bound is equal or less than
            <code>X</code>.</li>
        <li>Autovect branch has been reopened:
            (<a href= "https://gcc.gnu.org/ml/gcc/2007-01/msg00117.html">
            https://gcc.gnu.org/ml/gcc/2007-01/msg00117.html</a>).</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2006-11-27</dt>
     <dd>
     <ol>
        <li>Vectorization of loops that operate on multiple data-types, including type
            conversions: incorporated into GCC 4.3.</li>
        <li>Vectorization of non consecutive (non-unit-stride) data-accesses with power-of-2 strides:
            incoporated into GCC 4.3.</li>
        <li>Additional vectorizer related projects planned for GCC 4.3 can be found here:
            (<a href= "https://gcc.gnu.org/wiki/AutovectBranchOptimizations">
            https://gcc.gnu.org/wiki/AutovectBranchOptimizations</a>).</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2006-02-19</dt>
     <dd>
     <ol>
        <li>Vectorization of loops that operate on multiple data-types, including type
            conversions: submitted for incorporation into GCC 4.2.</li>
        <li>Detection and vectorization of special idioms, such as dot-product and widening-summation:
            Incorporated into GCC 4.2.</li>
        <li>Vectorization of non consecutive (non-unit-stride) data-accesses with power-of-2 strides:
            Incoporated into autovect-branch. To be submitted to GCC 4.2.</li>
     </ol>
     </dd>
</dl>

<dl>
  <dt>2005-10-23</dt>
    <dd>Autovect-branch has been enhanced to support the following features:
    <ol>
        <li>Vectorization of loops that operate on multiple data-types, including type
          promotion (conversion to a wider type) and type demotion (conversion to a narrower
          type). Type promotion is supported using the new <code>VEC_UNPACK_HI</code> and <code>VEC_UNPACK_LO</code>
          tree-codes (and the new <code>vec_unpacks_hi/lo</code> and <code>vec_unpacku_hi/lo</code> optabs). Type
          demotion is supported using the new <code>VEC_PACK_MOD</code> tree-code (and the new <code>vec_pack_mod</code>
          optab).</li>
        <li>Vectorization of idioms that involve type conversion. This allows more efficient
          vectorization (if specialized target support is available) that avoids the data
          packing/unpacking that is otherwise required to handle multiple data-types. These
          idioms include: widening-summation (<code>WIDEN_SUM</code>), dot-product (<code>DOT_PROD</code>),
          widening-multiplication (<code>WIDEN_MULT</code>, <code>VEC_WIDEN_MULT_HI/LO</code>), multiply-highpart
          (<code>MULT_HI</code>) and sum-of-absolute-differences (<code>SAD</code>).</li>
    </ol>
    </dd>
</dl>

<dl>
  <dt>2005-08-11</dt>
    <dd>The following enhancements have been incorpoated into GCC 4.1:
    <ol>
        <li>Vectorization of reduction has been introduced and currently supports summation,
          and minimum/maximum computation.</li>
        <li>Vectorization of conditional code has been introduced.</li>
        <li>The mechanism of peeling a loop to force the alignment of data accesses has been
          improved. We now generate better code when the misalignment of an access is known at
          compile time, or when different accesses are known to have the same
          misalignment, even if the misalignment amount itself is unknown. </li>
        <li>Dependence distance is considered when checking dependences between data references.</li>
        <li>Loop-closed-ssa-form is incrementally updated during vectorization.</li>
        <li>Generic parts of the data references analysis were cleaned up and externalized to make
          this analysis available to other passes.</li>
    </ol>
    </dd>
</dl>

<dl>
  <dt>2005-04-05</dt>
    <dd>Vectorization of reduction on autovect-branch was enhanced to support
        maximum/minimum computations, and special reduction idioms such as widening
        summation as a step towards supporting patterns like dot-product, sum of
        absolute differences and more:
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2005-04/msg00532.html">
            https://gcc.gnu.org/ml/gcc-patches/2005-04/msg00532.html</a>).</dd>
</dl>

<dl>
  <dt>2005-03-01</dt>
    <dd>Vectorization projects for GCC 4.1: See
      <a href=
            "https://gcc.gnu.org/wiki/Autovectorization_Enhancements">
             https://gcc.gnu.org/wiki/Autovectorization_Enhancements</a>. </dd>
    <dd>Vectorization capabilities in GCC 4.0: See
      <a href="#status4.0">2005-03-01 mainline status</a>. </dd>
</dl>

<dl>
  <dt>2005-02-25</dt>
    <dd>New features:
    <ol>
        <li>Summation is the first reduction idiom that is vectorized
        (autovect-branch only).</li>
        <li>Verbosity levels for vectorization reports.</li>
        <li>Improved line number information.</li>
        <li>Revised data-references analysis.</li>
    </ol>
    </dd>
</dl>

    <dl>
        <dt><strong>2005-03-01, autovect-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Vectorization is restricted to inner most countable loops,
                in which all operations operate on data types of the same size,
                and all memory accesses are consecutive.</li>

                <li>Certain forms of conditional code.</li>

                <li>Unaligned memory accesses are handled using loop peeling,
                or loop versioning, or direct misalignment support.</li>

                <li>Summation reduction is supported (<code>sum += a[i]</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>

                <li>Vectorization of the subtract-and-saturate idiom is supported.</li>
            </ol>
        </dd>
    </dl>

    <dl>
        <dt id="status4.0"><strong>2005-03-01, mainline (final 4.0 status)</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Vectorization is restricted to inner most countable loops,
                in which all operations operate on data types of the same size,
                and all memory accesses are consecutive.</li>

                <li>Unaligned memory write accesses are handled using loop peeling.
                This allows vectorization when there's only a single unaligned
                memory-write (or all memory-writes in the loop have the same
                misalignment). Unaligned memory read accesses are handled using
                direct misalignment support. This support is
                currently available for Alpha ev6, mmx, and altivec.</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>

                <li>No reductions (<code>sum += a[i]</code>) or inductions
                (<code>a[i] = i</code>).</li>

                <li>-ftree-vectorizer-verbose=[n] controls vectorization reports,
                with n ranging from 0 (no information reported) to 6 (all information
                reported).</li>
            </ol>
        </dd>
    </dl>

    <dl>
      <dt><strong>2005-02-02</strong></dt>
      <dd>New features that are only in autovect-branch:
      <ol>
        <li>Incrementally preserve loop closed SSA form during vectorization.</li>
        <li>Loop versioning guarded by a runtime alignment test.</li>
        <li>Idiom recognition, and vectorization of the subtract-and-saturate idiom.</li>
        <li>Incrementally preserve SSA form during vectorization.</li>
        <li>Improved handling of misalignment in case it is known at compile time,
        or in case multiple accesses are known to have the same misalignment.</li>
        <li>Vectorization of conditional code.</li>
        <li>Consider dependence distance.</li>
      </ol> 
      </dd>
    </dl>

    <dl>
        <dt><strong>2004-10-27, mainline</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no if-then-else).</li>

                <li><strong>New: No restrictions on the loop bound.</strong>
                An epilog loop is generated to handle unknown loop bounds
                and loop bounds that do not divide by the vectorization factor.</li>

                <li>Supported memory accesses are
                multidimensional arrays, and pointers that
                are annotated as <code>__restrict__</code>.</li>

                <li>All memory accesses are consecutive (stride=1).</li>

                <li><strong>New: Loops with a single unaligned write to memory
                (store).</strong> This is supported by peeling the loop to
                force the alignment of the store.</li>

                <li>Reads from memory (loads) can be unaligned. This support is
                currently available for Alpha ev6, mmx, and altivec.</li>

                <li>All operations operate on data types of the same
                size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or inductions
                (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>
            </ol>
        </dd>
    </dl>

    <dl>
      <dt><strong>2004-11-10</strong></dt>
      <dd>New branch for vectorization development opened: autovect-branch.
          lno-branch was retired.
          (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-11/msg00852.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-11/msg00852.html</a>).</dd>
    </dl>

    <dl>
       <dt><strong>2004-10-27</strong></dt>
       <dd>Mainline merge in progress. Last pending vectorization patches for
       mainline:</dd>
       <dd>Support for vectorization of conditional code
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01768.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01768.html</a>).</dd>
       <dd>Consider dependence distance
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-10/msg01046.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-10/msg01046.html</a>).</dd>
    </dl>

   <dl>
     <dt><strong>2004-10-14</strong></dt>
     <dd>Support for unknown loop bound
       (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01104.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01104.html</a>,
       vectorizer merge part #2) committed to mainline.</dd>
     <dd>Peeling for alignment
       (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01894.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01894.html</a>,
       vectorizer merge part #5) committed to mainline.</dd>
   </dl>

    <dl>
        <dt><strong>2004-09-27, mainline</strong></dt>

        <dd>
	    Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no if-then-else).</li>

                <li>The loop bound (number of iterations) is known and
                divides by the vectorization factor.</li>

                <li><strong>New:</strong> Supported memory accesses are
                <strong>multi</strong>-dimensional arrays, and pointers that
                are annotated as <code>__restrict__</code>.</li>

                <li><strong>New: Additional forms of accesses are supported:
                </strong> Restrictions on the the initial value of the
                access function of pointers and array indexes have been
                relaxed. These can now take a form like
                <code>p=&amp;a[16]-4B</code> (pointer), and
                <code>a[i+off]</code> (arrays).</li>

                <li>All memory accesses are consecutive (stride=1).</li>

                <li>Writes to memory (stores) are aligned.</li>

                <li><strong>New: Reads from memory (loads) can be
                unaligned.</strong></li>

                <li>All operations operate on data types of the same
                size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or inductions
                (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>
            </ol>
        </dd>
    </dl>

    <dl>
      <dt><strong>2004-09-23</strong></dt>
      <dd>Support for unaligned loads
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01522.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01522.html</a>,
        vectorizer merge part #4) committed to mainline.</dd>
    </dl>

    <dl>
      <dt><strong>2004-09-19</strong></dt>
      <dd>Support for additional forms of data references
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01521.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-09/msg01521.html</a>,
        vectorizer merge part #3) committed to mainline.</dd>
    </dl>

    <dl>
        <dt><strong>2004-09-13, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>Supported memory accesses are multi-dimensional arrays,
                and pointers that are annotated as
                <code>__restrict__</code>.</li>

               <li><strong>New: Additional forms of accesses are supported:
               </strong> Restrictions on the the initial value of the access
               function of pointers and array indexes have been relaxed.
               These can now take a form like <code>p=&amp;a[16]-4B</code>
               (pointer), and <code>a[i+off]</code> (arrays).</li>

                <li>All memory accesses are consecutive (stride=1)
                and aligned.</li>

                <li>Writes to memory (stores) are aligned.</li>

                <li><strong>New: Reads from memory (loads) can be
                unaligned.</strong></li>

                <li>Loop versioning for alignment is applied to unaligned
                stores.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>
            </ol>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-09-02, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li><strong>New:</strong> The loop bound (number of
                iterations) can be unknown at compile time, <strong>or
                can be known but not divisible by the vectorization
                factor.</strong></li>

                <li><strong>New</strong>: Supported memory accesses are
                <strong>multi</strong>-dimensional arrays, and pointers
                that are annotated as <code>__restrict__</code></li>

                <li>All memory accesses are consecutive (stride=1).</li>

                <li><strong>New: Loop versioning for alignment:</strong>
                in the presence of unaligned accesses create two versions
                of the loop controlled by a runtime alignment check. In one
                version all the accesses are guaranteed to be aligned, and
                it can therefore be vectorized. In the second version there
                may be unaligned accesses, and it remains unvectorized.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).</li>
            </ol>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-08-17, mainline</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop bound (number of iterations) is known
                and divides by the vectorization factor.</li>

                <li>Supported memory accesses are one-dimensional
                arrays, whose alignment can be forced (not
		<code>extern</code>,
                and stack boundary of target platform allows it),
                and aligned pointers that are annotated as
                <code>__restrict__</code>.</li>

                <li>All memory accesses are consecutive (stride=1)
                and aligned.</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] =
                x</code>).</li>
            </ol>

            <p>Examples of vectorizable loops: <a href=
            "#example1">loop</a>, <a href="#example5">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-08-17, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>The loop bound (number of iterations) can be
                unknown.</li>

                <li><strong>New</strong>: Supported memory accesses
                are <strong>multi</strong>dimensional arrays, whose
                alignment can be forced (not extern), and aligned
                pointers that are annotated as
                <code>__restrict__</code>.</li>

                <li>All memory accesses are consecutive (stride=1)
                and aligned.</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] =
                x</code>).</li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example8">loop</a></p>
        </dd>
    </dl>

    <dl>
      <dt><strong>2004-08-17</strong></dt>
      <dd>Initial vectorization functionality committed to mainline
        (<a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-08/msg01219.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-08/msg01219.html</a>,
         <a href=
            "https://gcc.gnu.org/ml/gcc-patches/2004-07/msg02127.html">
            https://gcc.gnu.org/ml/gcc-patches/2004-07/msg02127.html</a>,
        vectorizer merge part #1).</dd>
   </dl>

    <dl>
        <dt><strong>2004-07-20, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>The loop bound (number of iterations) can be
                unknown.</li>

                <li><strong>New</strong>: Supported memory accesses
                are one-dimensional arrays, <strong>whose base can
                be a struct field,</strong> and whose alignment can
                be forced (not extern arrays), and aligned pointers
                that are annotated as
                <code>__restrict__</code>.</li>

                <li>All memory accesses are consecutive (stride=1)
                and aligned. Arrays are alignable</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] =
                x</code>).</li>

                <li><strong>New: first gfortran program
                vectorized.</strong></li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example5">loop</a>, <a href="#example6">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-06-25, apple-ppc-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>The loop bound (number of iterations) can be
                unknown.</li>

                <li>Supported memory accesses are one-dimensional
                arrays, and pointers. If more than one memory
                access is present in the loop, any pointers that
                are used in the loop have to be annotated as
                <code>__restrict__</code>.</li>

                <li>Store (memory-write) accesses have to be
                aligned.</li>

                <li><strong>New:</strong> Loads (memory-reads) can
                be unaligned <strong>by an unknown amount (e.g.
                access <code>a[i+x]</code>, where the value of x is
                unknown).</strong> <strong>Misalignment support for
                loads was also made more efficient.</strong></li>

                <li>All memory accesses are consecutive
                (stride=1).</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>Some forms of if-then-else patterns can be
                vectorized.</li>

                <li><strong>New: Infrastructure for idiom
                recognition has been added. The first computation
                idiom that is recognized and vectorized is a
                multiplication of unsigned chars, whose (unsigned
                short) product is converted back to unsigned char
                (a similar computation comes up in pixel blending;
                we support a simplified version that does not
                require operating on different data
                types).</strong></li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] = x</code>).
                <strong>New: Support for invariants was made more
                efficient.</strong></li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example7">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-06-23, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>The loop bound (number of iterations) can be
                unknown.</li>

                <li>Supported memory accesses are one-dimensional
                arrays, whose alignment can be forced (not extern
                arrays).</li>

                <li><strong>New: Memory accesses can also be
                pointer based. If more than one memory access is
                present in the loop, any pointers that are used in
                the loop have to be annotated as
                <code>__restrict__</code>. The pointers have to
                point to an aligned address.</strong></li>

                <li>All memory accesses are consecutive (stride=1)
                and aligned.</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] =
                x</code>).</li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example3">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-06-17, apple-ppc-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>The loop bound (number of iterations) can be
                unknown.</li>

                <li>Memory accesses are one dimensional-arrays,
                whose alignment can be forced (not extern
                arrays).</li>

                <li><strong>New: Memory accesses can also be
                pointer based. If more than one memory access is
                present in the loop, any pointers that are used in
                the loop have to be annotated as
                <code>__restrict__</code>. (new experimental
                feature)</strong></li>

                <li><strong>New: Loads (memory reads) can be
                unaligned by a known amount (e.g. access
                <code>a[i+1]</code>, where array <code>a</code> is
                aligned and <code>i</code> starts from 0)</strong>.
                Stores (memory writes) still have to be
                aligned.</li>

                <li>All memory accesses are consecutive
                (stride=1).</li>

                <li>Supportable operations include plus/minus/mult,
                as well as bitwise operations -
                and/or/xor/1's-complement, according to available
                vector support on the target platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li><strong>New: Some forms of if-then-else
                patterns can be vectorized. (new experimental
                feature)</strong>.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>Constants and invariants are supported
                (<code>a[i] = 5</code>, <code>a[i] =
                x</code>).</li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example4">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-06-04, lno-branch (and
        apple-ppc-branch)</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li><strong>New: No restrictions on the form of the
                loop index and the loop exit
                condition.</strong></li>

                <li><strong>New: The loop bound (number of
                iterations) can be unknown</strong>. Currently
                known loop-bounds still need to be divisible by the
                vectorization factor.</li>

                <li>All memory accesses are one dimensional-arrays,
                whose alignment can be forced (not extern
                arrays).</li>

                <li>All array accesses are consecutive and aligned;
                i,e. all the array references are of the form
                <code>a[i]</code>, where <code>i</code> is updated
                from 0 to N in steps of 1.</li>

                <li><strong>New:</strong> Supportable operations
                include plus/minus/mult, <strong>as well as bitwise
                operations - and/or/xor/1's-complement</strong>,
                according to available vector support on the target
                platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li><strong>New: Constants and invariants are
                supported (<code>a[i] = 5</code>, <code>a[i] =
                x</code>)</strong>.</li>
            </ol>

            <p>Examples of newly vectorizable loops: <a href=
            "#example2">loop</a></p>
        </dd>
    </dl>

    <dl>
        <dt><strong>2004-01-01, lno-branch</strong></dt>

        <dd>
            Description of vectorizable loops:

            <ol>
                <li>Inner most loops that consist of a single
                basic block (i.e, straight-line code, no
                if-then-else).</li>

                <li>The loop has to be countable - i.e, the number
                of iterations can be evaluated before the loop
                starts to execute.</li>

                <li>Known (constant) loop bound, divisible by the
                vectorization factor.</li>

                <li>The loop index <code>i</code> is updated from 0
                to N in steps of 1, and the loop exit condition is
                of the form <code>i&lt;N</code>.</li>

                <li>All memory accesses are one dimensional-arrays,
                whose alignment can be forced (not extern
                arrays).</li>

                <li>All array accesses are consecutive (stride=1)
                and aligned.</li>

                <li>Supportable operations include plus/minus/mult,
                according to available vector support on the target
                platform.</li>

                <li>All operations operate on data types of the
                same size.</li>

                <li>No reductions (<code>sum += a[i]</code>) or
                inductions (<code>a[i] = i</code>).</li>

                <li>No Constants or invariants in the loop
                (<code>a[i] = 5</code>).</li>
            </ol>

            <p>Examples of vectorizable loops: <a href=
            "#example1">loop</a></p>
        </dd>
    </dl>

    <h2 id="References">References/Documentation</h2>
    <ol>
        <li>"Vapor SIMD: Auto-vectorize once, run everywhere",
	Dorit Nuzman, Sergei Dyshel, Erven Rohou, Ira Rosen, Kevin Williams,
	David Yuste, Albert Cohen, Ayal Zaks, CGO 2011: 151-160</li>

        <li>"Polyhedral-Model Guided Loop-Nest Auto-Vectorization", 
        Konrad Trifunovic, Dorit Nuzman, Albert Cohen, Ayal Zaks and Ira Rosen,   
        PACT 2009</li>

        <li>"Outer-loop vectorization: revisited for short SIMD architectures",
        Dorit Nuzman and Ayal Zaks, PACT 2008</li>
        
        <li>"Loop-Aware SLP in GCC", Ira Rosen, Dorit Nuzman
        and Ayal Zaks, GCC summit, July 2007.
	<a href="https://gcc.gnu.org/pub/gcc/summit/2006-GCC-Summit-Proceedings.pdf">GCC Summit 2007 Proceedings</a></li>

        <li>"Autovectorization in GCC - two years later", Dorit Nuzman and Ayal Zaks, 
        GCC summit, June 2006.
        <a href="http://www.gccsummit.org/2006/2006-GCC-Summit-Proceedings.pdf">
        http://www.gccsummit.org/2006/2006-GCC-Summit-Proceedings.pdf</a></li>

	<li>"Auto-Vectorization of Interleaved Data for SIMD",
	Dorit Nuzman, Ira Rosen and Ayal Zaks. 
	ACM SIGPLAN 2006 Conference on  Programming Language Design 
	and Implementation (PLDI), Ottawa, Canada, June 10-16, 2006.</li>

	<li>"Multi-platform Auto-vectorization", Dorit Nuzman and 
	Richard Henderson, CGO-4 (The 4th Annual International 
	Symposium on Code Generation and Optimization), March 26-29, 2006, 
	Manhattan, New York.</li>

        <li>"Autovectorization in GCC", Dorit Naishlos, GCC summit, June 2004.
        <a href="https://gcc.gnu.org/pub/gcc/summit/2004/Autovectorization.pdf">
        https://gcc.gnu.org/pub/gcc/summit/2004/Autovectorization.pdf</a></li>

        <li>"The Software Vectorization Handbook. Applying Multimedia
        Extensions for Maximum Performance.", Aart Bik, Intel Press,
        June 2004.</li>

        <li>"Vectorization for SIMD Architectures with Alignment
        Constraints", Alexandre E. Eichenberger, Peng Wu, Kevin O'brien,
        PLDI'04, June 9-11 2004.</li>

        <li id="kenedy-book">"Optimizing
        Compilers for Modern Architectures - A dependence based
        approach", Randy Allen &amp; Ken Kennedy, Morgan Kaufmann
        Publishers, San Francisco, San Diego, New York (2001).</li>

        <li>"Exploiting Superword Level Parallelism with Multimedia
        Instruction Sets", Samuel Larsen and Saman Amarasinghe,
        PLDI 2000.</li>
    </ol>

    <h2 id="high-level">High-Level Plan of Implementation (2003-2005)</h2>

    <p>The table below outlines the high level vectorization scheme
    along with a proposal for an implementation scheme, as
    follows:</p>

    <ul>
        <li>
            <p>The first column ("vectorization driver") lists the
            tasks that the vectorizer must consist of. It briefly
            describes the expected functionality of each task.</p>
        </li>

        <li>
            <p>The second column ("basic-vectorizer") describes a
            proposal for a basic vectorizer that provides minimal
            support for each of these tasks, listing the
            restrictions that will be imposed by the basic
            vectorizer on candidate loops. Loops that are
            considered vectorizable by the basic-vectorizer are of
            the form: <code>for(i=0; i&lt;N; i++) {a[i] = b[i] +
            c[i]; }.</code> The "basic vectorizer" was implemented by
            Dorit (Naishlos) Nuzman.</p>
        </li>

        <li>
            <p>The third column ("enhancements") lists possible
            directions for extending the capabilities of the basic
            vectorizer. Some of these enhancements are aimed at
            improving the quality of the vector code that is being
            generated. Other enhancements aim at broadening the
            range of computations that are amenable for
            vectorization. Other focus on improved robustness.
            Following the table is a complete and detailed list of
            these enhancements. Next to each item which is already
            being addressed, there should be the name of the
            relevant contact person.</p>
        </li>
    </ul>

    <table class="border">
        <tbody>
            <tr>
                <th class="width33">vectorization driver</th>

                <th class="width33">basic vectorizer</th>

                <th class="width33">enhancements</th>
            </tr>

            <tr class="top">
                <td>
                    <code>analyze_loop_CFG(loop)</code>

                    <p>Checks the <a href="#loopCFG">control flow
                    properties of the loop</a> (number of
                    basic-blocks it consists of, nesting, single
                    entry/exit, etc.), in order to determine
                    whether the control flow of the loop falls
                    within the range of loop forms that are
                    supported by this vectorizer.</p>
                </td>

                <td>
                    <ul>
                        <li>inner-most (single nest) loops.</li>

                        <li>single basic block loops; i.e., no
                        if-then-else constructs, etc. (in practice
                        this means loops that consist of exactly
                        two basic blocks - header+latch).</li>

                        <li>other restrictions (single
                        successor/predecessor, a pre-header
                        block).</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>use <a href="#IdiomRecognition">idiom
                        recognition</a> to collapse
                        <code>if-then-else</code> constructs into a
                        straight line code.</li>

                        <li>handle <a href="#cond">conditional
                        execution</a></li>

                        <li>the above needs to be aware of <a href=
                        "#Machine">target specific vector
                        capabilities</a>.</li>

                        <li>extend the <a href="#LoopForms">range
                        of loop forms</a> that can be vectorized,
                        with respect to their CFG
                        characteristics.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p>
                    <code>analyze_loop_index_and_bound(loop)</code></p>

                    <p>Analyzes the loop termination condition to
                    determine the loop bound and properties of the
                    loop index (its bounds and step). The
                    functionality of this utility should be largely
                    provided by the information computed by the
                    <a href="#InductionVariable">Induction Variable
                    Analyzer</a>.</p>
                </td>

                <td>
                    <ul>
                        <li>handle simple normalized loops (loop
                        index is a trivial IV with step 1, etc.),
                        with a simple termination condition.</li>

                        <li>loop-bound known at compile time.</li>

                        <li><code>loop-bound &gt;= vector_size</code>
                        and <code>loop-bound % vector_size =
                        0</code>.</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>relax the restrictions on the <a href=
                        "#LoopForms">loop bound</a> and <a href=
                        "#AccessPattern">loop index</a> imposed by
                        the basic vectorizer.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p><code>analyze_loop_stmts(loop-stmts)</code></p>

                    <p>Scan the loop statements and check whether
                    there are any statements that prohibit
                    vectorization (function calls, statements that
                    don't have a mapping to a built-in vector
                    function, etc.)</p>
                </td>

                <td>
                    <ul>
                        <li>simple operations for which there's a
                        1-1 mapping between the scalar and vector
                        operations.</li>

                        <li>no support for scalar expansion,
                        induction variables, reduction
                        operations...</li>

                        <li>no mixture of data types (all
                        statements operate on the same data
                        types).</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>handle <a href="#computations">scalar
                        expansion</a>.</li>

                        <li>handle computations with <a href=
                        "#computations">mixed data types</a>.</li>

                        <li>Support operations that can't be
                        expressed using existing (scalar)
                        tree-codes; this requires <a href=
                        "#Machine">developing a mechanism to expose
                        to the compiler that such operations are
                        supportable</a>.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p>
                    <code>analyze_access_pattern(loop-mem-refs)</code></p>

                    <p>Analyze the memory references in the loop,
                    and <a href="#AccessPattern">classify them
                    according to the access pattern</a> that they
                    exhibit.</p>
                </td>

                <td>
                    <ul>
                        <li>support only memory accesses which are
                        array references (no pointers...).</li>

                        <li>support only consecutive (unit stride)
                        access pattern.</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>extend the access pattern analyzer to
                        handle pointer references</li>

                        <li>improve the <a href=
                        "#PointerAliasing">memory aliasing</a>
                        capabilities.</li>

                        <li>handle non consecutive access patterns
                        <a href="#Machine">if supported by the
                        target</a>.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p>
                    <code>analyze_alignment(loop-mem-refs)</code></p>

                    <p>Analyze the alignment of the memory
                    references in the loop. For each memory
                    reference, record its misalignment amount, if
                    it can be resolved at compile time.</p>
                </td>

                <td>
                    <ul>
                        <li>misalignment amount for all memory
                        references is known at compile time.</li>

                        <li>misalignment is zero for all references
                        (all references are aligned).</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li><a href="#Alignment">handle unaligned
                        accesses</a>.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p>
                    <code>analyze_loop_carried_dependences(loop)</code></p>

                    <p>Build the loop dependence graph (for scalar
                    and array references); Detect Strongly
                    Connected Components (SCCs) in the graph
                    (statements that are involved in a dependence
                    cycle); Perform a topological sort on the
                    reduced graph (in which each SCC is represented
                    by a single node); Only singleton nodes w/o
                    self dependencies can be vectorized. If other
                    (compound) nodes (which represent SCCs) are
                    present, loop transformations are required.</p>
                </td>

                <td>
                    <ul>
                        <li>handle only loops that do not contain
                        any SCCs (i.e., no dependence cycles).</li>

                        <li>the only scalar loop-carried
                        dependencies allowed are of IVs which are
                        used in array references or for the loop
                        index (i.e., reduction is not
                        supported).</li>

                        <li>use simplest dependence tests.</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>use more <a href="#Dependence">advanced
                        dependence tests</a>.</li>

                        <li>try to <a href="#Dependence">break
                        cycles in the dependence graph</a> of the
                        loop by performing <a href=
                        "#LoopTransform">loop transformations</a>
                        (or <a href="#IdiomRecognition">detecting
                        reduction</a>).</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p>
                    <code>estimate_vectorization_profitability(loop)</code></p>

                    <p>At this point, it has been determined that
                    the loop is vectorizable. It remains to decide
                    whether it is indeed profitable to vectorize
                    it.</p>
                </td>

                <td>
                    <ul>
                        <li>vectorize all loops with loop_bound
                        &gt;= MIN_LIMIT (?).</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li>develop a <a href="#Cost">cost
                        model</a>.</li>
                    </ul>
                </td>
            </tr>

            <tr class="top">
                <td>
                    <p><code>vectorize_loop(loop)</code></p>

                    <p>Replace the scalar statements with the
                    corresponding vector statements (which could be
                    calls to builtin functions); Also change the
                    loop bound accordingly.</p>
                </td>

                <td>
                    <ul>
                        <li>use a <a href=
                        "#Machine">scalar-to-vector
                        mapping</a>.</li>
                    </ul>
                </td>

                <td>
                    <ul>
                        <li><a href="#OtherOptimizations.">misc.
                        optimizations</a>.</li>

                        <li><a href="#UserHints">user hints</a>
                        to consider.</li>
                    </ul>
                </td>
            </tr>
        </tbody>
    </table>

    <p>The following is a list of independent directions by which
    the basic vectorizer can be enhanced. It should be possible for
    different people to work on different items on this list. Some
    of these items are already under development, or (partially)
    supported.</p>

    <ol>
        <li>
	    <h3 id="loopCFG">>Loop detection and loop CFG analysis</h3>

            <p>Detect loops, and record some basic control flow
            information about them (contained basic blocks, loop
            pre-header, exit and entry, etc.).</p>

            <p><b>Status:</b> Loop detection and control flow
            analysis is already supported (<code>cfgloop.c</code>,
            <code>cfgloopanal.c</code>).</p>
        </li>

        <li>
            <h3 id="Machine">Modeling the target machine vector capabilities to
            the <code>tree</code>-level.</h3>

            <p>Expose the required target specific information to
            the <code>tree</code> level. This includes providing a
            mapping from scalar operations to the corresponding
            vector support, which will answer the following
            questions:</p>

            <ol>
                <li>Does vector support for this operation
                exist?</li>

                <li>At what cost?</li>

                <li>How to express the vector operation at the
                <code>tree-</code>level?</li>
            </ol>

            <p>The general SIMD support in GCC already provides
            some initial support; For simple operations which can
            be expressed using existing (scalar)
            <code>tree-codes</code> (<code>PLUS_EXPR, MULT_EXPR,</code>
            etc.) the existing infra-structure can provide answers
            for questions 1 and 2 above, however, the
            <code>tree-</code>level currently does not have an idea
            about the cost that this transformation actually
            entails. A first basic implementation will support only
            simple operations that fall into the above category. As
            the capabilities of the vectorizer are extended, it
            will be required to inform the vectorizer of the
            advanced capabilities available in the architecture
            (for example, support for operations on complex
            numbers, reduction, etc.). Such operations cannot be
            expressed using existing tree-codes. Possible
            solutions: introduce new tree-codes (and corresponding
            optabs); introduce new builtins that are exposed to the
            compiler; use target hooks to handle these cases (the
            hook could return a call to a machine specific builtin
            function). Another related design question that needs
            to be addressed here is how much information to expose
            to the tree-level (is it sufficient to indicate that
            conditional vector addition is supported, or do we want
            the vectorizer to actually generate the required
            masking/predication/select operations depending on the
            target? similarly for alignment, multiplication of
            integers, etc.).</p>

            <p><b>Status:</b> Open for discussion.<br />
            Related discussion:
	    <a href=
            "https://gcc.gnu.org/ml/gcc/2004-08/msg00317.html">
            https://gcc.gnu.org/ml/gcc/2004-08/msg00317.html</a></p>
        </li>

        <li>
            <h3 id="mapping">Enhance the Builtins Support</h3>

            <p>Currently the tree optimizers do not know the
            semantics of target specific builtin functions, so they
            do not attempt to optimize them (or to SSA the
            variables passed as arguments to these functions).
            Since the vectorizer will probably end up generating
            calls to target specific builtin functions, this
            situation needs to be improved, i.e. - the semantics of
            these builtins needs to somehow be exposed to the
            compiler.</p>

            <p><b>Status:</b> Open for discussion.</p>
        </li>

        <li>
            <h3 id="cost">Cost Model</h3>

            <p>There is an overhead associated with vectorization
            -- moving data in to/out of vector registers
            before/after the vectorized loop, aligning of data
            accesses, etc. It is required to incorporate a cost
            model into the machine description in order to allow
            the vectorizer to evaluate whether it is worth while to
            vectorize a given loop. One can also consider using run
            time tests to decide which version of the loop to
            execute (scalar or vectorized).</p>

            <p><b>Status:</b> Open for discussion.<br />
            Related discussion: <a href=
            "https://gcc.gnu.org/ml/gcc-patches/2003-09/msg00469.html">
            https://gcc.gnu.org/ml/gcc-patches/2003-09/msg00469.html</a></p>
        </li>

        <li>
            <h3 id="InductionVariable">Induction Variable Analysis</h3>

            <p>Used by the vectorizer to detect loop bound, analyze
            access patterns and analyze data dependencies between
            array references. One option is that the dependence
            tests would be designed deal with array references that
            are expressed in terms of a linear function of the
            iteration counter (in this case, vectorization will
            also benefit from optimizations like induction variable
            substitution and replacement of auxiliary IVs with
            linear functions of the loop index). A dependence
            tester that is based on IVs represented in this form
            would analyze each subscript of each array reference,
            and apply the appropriate dependence test (SIV, ZIV,
            MIV etc., see <a href="#Dependence">dependence
            testing</a>). Alternatively, an induction variable
            evolution analyzer could provide a different
            implementation to the dependence tester. This is the
            solution that is currently used, based on the Induction
            Variable evolution analysis developed by Sebastian
            Pop.</p>

            <p><b>Status:</b> Using the IV evolution analyzer
            developed by Sebastian Pop.</p>
        </li>

        <li>
	    <h3 id="dependence">Dependence Testing</h3>

            <p>Following the classic dependence-based approach for
            vectorization as described in <a href=
            "#kenedy-book">[1]</a>, apply dependence tests to pairs
            of array references in each loop nest, and analyze the
            resulting dependence graph. We will start from a
            dependence analyzer that relies on the array references
            being expressed in terms of a linear function of the
            loop index, apply the simplest dependence tests to all
            pairs of memory read/write and write/write, and
            gradually extend its capabilities. The scheme below
            follows the algorithm described in <a href=
            "#tseng">[2]:</a></p>

            <ul>
                <li>Partition the array subscripts into separable
                sets (subscripts which index does not occur in
                other subscripts), and apply the simplest tests for separable
                subscripts (strong SIV (single index variable)
                tests). [done]</li>

                <li>Incorporate more advanced dependence tests;
                first, tests for separable subscripts - e.g., weak
                SIV tests, MIV (Multiple Index Variable) tests,
                followed by tests for coupled subscripts, possibly
                up to integer linear programming like
                Fourier-Motzkin elimination.
		[some of these have been implemented]</li>

                <li>Compute dependence distance, and prune
                dependencies with distance &gt; vector_size. [done]</li>

                <li>Try to handle cycles in the dependence graph of
                the loop (by performing loop distribution,
                etc.).</li>

                <li>Generalize the dependence tester to nested
                loops.</li>
            </ul>

            <p><b>Status:</b> Many of the tests above are implemented.
            Omega test is in the works. We don't have a DDG graph
            built based on the dependence tests.</p>
        </li>

        <li>
            <h3 id="AccessPattern">Access Pattern Analysis</h3>

            <p>The memory architecture usually allows only
            restricted accesses to data in memory; one of the
            restrictions is that the accessed data must be
            consecutive in memory. Any other accesses (strided for
            example) require to perform special permutation of the
            data in order to pack the data elements in the right
            order into a vector register. Support for different
            access patterns consists of the following stages:</p>

            <ul>
                <li>Classify the access pattern of each array
                reference.[done, using the scalar evolution analyzer]</li>

                <li>Trivially handle consecutive (unit stride)
                access patterns (a[i]). [done]</li>

                <li>Handle strided access patterns (a[2*i]). The
                stride 2 access pattern appears in computations on
                complex numbers, where the real and imaginary parts
                are interleaved in the input/output array. [done]</li>

                <li>Handle other types of access patterns, e.g. reverse access,
                strides that are not a power-of-2. </li>

                <li>Support pointer arithmetic. [done]</li>
            </ul>

	    <p><b>Status:</b> Partial support in place.</p>

        </li>

        <li>
            <h3 id="computations">Extend the range of supportable operations</h3>

            <p>At first, the only computations that will be
            vectorized are those for which the vectorization
            process consists of trivially replacing each scalar
            operation in the loop with its vector counterpart. This
            includes simple loads, stores and arithmetic operations
            that operate on the same data type. Some computations
            require extra code to be generated in order to
            vectorize. These include:</p>

            <ul>
                <li>computations with mixed types; these require
                proper promotion/demotion between vectors of
                different sizes. [done]</li>

                <li>computations that involve loop invariants
                (<code>a[i] = N</code>) and require scalar
                expansion. [done]</li>

                <li>computations that involve induction variables
                (<code>a[i] = i</code>), require scalar expansion, and
                proper initialization and update code.
		[planned]</li>

            </ul>

            <p><b>Status:</b> Partial support in place.</p>

        </li>

        <li>
            <h3 id="alignment">Alignment</h3>

            <p>The memory architecture usually allows only
            restricted accesses to data in memory. One of the
            restrictions is that data accesses need to be properly
            aligned on a certain boundary. Even if the architecture
            supports unaligned accesses, these are usually much
            more costly than aligned accesses. The work on
            alignment consists of several stages:</p>

            <ul>
                <li>Compute the misalignment properties of each
                memory access. [Initial support in place. 
                Contact: Daniel Berlin]</li>

                <li>Handling of aligned memory accesses only (do
                not attempt to vectorize loops that contain
                unaligned accesses). [done]</li>

                <li>If it is impossible to determine at compile
                time whether the memory access is aligned, <a href=
                "#versioning">create two versions of the loop and
                use a runtime test</a> to decide which version to
                execute: the original scalar version (if the data
                access is not aligned), or the vectorized version
                (if the access is aligned). [done. Contact: Keith Besaw]</li>

                <li>Develop optimizations that increase the
                alignment of data accesses (static loop peeling,
                dynamic loop peeling, etc.). [done. Contact: Olga Golovanevsky]</li>

                <li>Vectorize unaligned accesses. There are
                different ways to do that, depending on whether the
                target supports unaligned accesses, and also
                depending on what we want to implement at the tree
                level, and what we want to leave for the RTL level
                to handle. [done for loads]</li>

                <li>Build a cost model to decide when to apply
                loop-peeling and/or loop-versioning to force alignment,
                and when to generate unaligned vector accesses.</li>
            </ul>

            <p><b>Status:</b> Currently the way we handle unaligned
            stores is by peeling the loop to force the alignment of
            the store. This is not always applicable. Vectorizing
            unaligned stores is in the works.</p>
        </li>

        <li>
            <h3 id="IdiomRecognition">Idiom Recognition</h3>

            <p>It is often the case that complicated computations
            can be reduced into a simpler, straight-line sequence
            of operations. These operations may not be directly
            supported in a scalar form, but are supported by the
            target in a vector form. Such cases include:</p>

            <ul>
                <li>Reduction operations:

                    <ul>
                        <li>Detect different kinds of reduction
                        (summation, min/max, min/max with index,
                        etc.); once detected, these idioms may be
                        replaced with a virtual scalar operation
                        (to facilitate straight forward vector code
                        generation). [done] </li>

                        <li>Vectorizing the reduction requires
                        generating epilog code after the loop.
                        First, generate a scalar code sequence to
                        compute the epilog. Later, try to make use
                        of target dependent mechanisms to compute
                        the epilog of the reduction more
                        efficiently. [done] </li>
                    </ul>
                </li>

                <li>Special patterns that are supported by the
                architecture. <a href="#cond">This may involve
                collapsing multi-block constructs (such as
                <code>if-then-else</code>)</a> into a single
                vectorizable operation. For example, in the
                following code sequence (taken from the SPECint
                benchmark gzip) the conditional expression can be
                collapsed into a "subtract and saturate" operation
                (see <a href=
                "https://gcc.gnu.org/ml/gcc/2003-07/msg01355.html">
                    https://gcc.gnu.org/ml/gcc/2003-07/msg01355.html</a>):

<pre>
for (n = 0; n &lt; HASH_SIZE; n++)
  {
    m = head[n];
    head[n] = (Pos)(m &gt;= 32768 ? m-32768 : 0);
  }

</pre>
                </li>

                <li>Detect saturation idioms, and map them to the
                appropriate vector operation. [initial support in place. 
		See <a href=
                "https://gcc.gnu.org/ml/gcc-patches/2004-12/msg00931.html">
                https://gcc.gnu.org/ml/gcc-patches/2004-12/msg00931.html</a>]</li>
            </ul>

            <p><b>Status:</b> Partial support in place.</p>
        </li>

        <li>
            <h3 id="cond">Conditional Execution</h3>

            <p>The general principle we are trying to follow is to
            keep the actual code transformation part of the
            vectorizer as simple as possible: a simple scan of
            straight-line code, and a one-to-one replacement of
            each scalar operation with the equivalent vector
            operation. To support this scheme in the presence of
            conditional execution, we'll need to flatten the loop
            body by collapsing if-then-else into a conditional
            (scalar) operation (something like transforming -
            '<code>if (x) {c = PLUS (a,b)}</code>' into
            '<code>PLUS_COND(a,b,x)</code>'. These will later be
            replaced with a conditional vector operation using
            whatever support is available on the target (masking,
            predication or select operation). Flattening the loop
            body this way will greatly simplify the vectorizer.
            Some of the issues to think about here: (a) how to
            represent these conditional operations, (b) to what
            extent does the tree vectorizer need to be aware of the
            specific target support that is available for
            conditional vector execution (mask/predicate/select),
            and (c) how to allow a simple way to reverse this
            transformation if the loop doesn't end up getting
            vectorized.</p>

            <p><b>Status:</b> Done. Contact: Devang Patel.</p>
        </li>

        <li>
            <h3 id="LoopForms">Handle Advanced Loop Forms</h3>

            <ol>
                <li>Support general loop bound (unknown, or doesn't
                divide by the vector size). [done. Contact: Olga
                Golovanevsky]</li>

                <li>Support more complex forms of loop termination
                condition and loop index update. [done]</li>

                <li>Support outer-loop vectorization (unroll and
                jam). [planned]</li>

                <li>Relax other restrictions on the loop form.</li>
            </ol>

            <p><b>Status:</b> Partial support in place.</p>
        </li>

        <li>
            <h3 id="PointerAliasing">Handle Pointer Aliasing</h3>

            <ol>
                <li>Improve aliasing analysis. [various GCC projects
		deal with improvements to alias analysis].</li>

                <li>Generate run-time tests for cases where memory
                anti-aliasing cannot be resolved at compile
                time. [Planned. Contact: Keith Besaw]</li>

                <li>Support user hints. [in the works. See <a href=
                "https://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html">
                https://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html</a>.
                Contact: Devang Patel]</li>
            </ol>

            <p><b>Status:</b> In the works. </p>
        </li>

        <li>
            <h3>Aliasing and Virtual def-use Chains</h3>

            <p>Address the item from the <a href=
            "index.html#todo">tree-ssa todo list</a> - "SSA
            information for arrays : The existing implementation
            treats arrays as an opaque object. A definition to an
            array location is treated as a definition for the whole
            array"</p>

            <p><b>Status:</b> Open for discussion.</p>
        </li>

        <li>
            <h3>Array addressing Represented as Pointer
            Arithmetic</h3>

            <p>Address the issue mentioned in <a href=
            "https://gcc.gnu.org/ml/gcc/2003-07/msg02013.html">
	    https://gcc.gnu.org/ml/gcc/2003-07/msg02013.html</a>,
            which turns out to be a front end issue.</p>

            <p><b>Status:</b> In the works. See <a href=
            "https://gcc.gnu.org/wiki/Array_references_on_pointers">
	    https://gcc.gnu.org/wiki/Array_references_on_pointers</a>
	    and <a href="https://gcc.gnu.org/ml/gcc-patches/2005-05/msg01577.html">
	    https://gcc.gnu.org/ml/gcc-patches/2005-05/msg01577.html</a>.</p>
        </li>

        <li>
            <h3 id="versioning">Loop versioning</h3>

            <p>Provide utilities that allow performing the
            following transformation: Given a condition and a loop,
            create -'if (condition) { loop_copy1 } else {
            loop_copy2 }', where loop_copy1 is the loop transformed
            in one way, and loop_copy2 is the loop transformed in
            another way (or unchanged). 'condition' may be a run
            time test for things that were not resolved by static
            analysis (overlapping ranges (anti-aliasing),
            alignment, etc.).</p>

            <p><b>Status:</b> Done. Contact: Devang Patel.</p>
        </li>

        <li>
            <h3 id="LoopTransform">Loop Transformations to Increase Vectorizability of
            Loops</h3>

            <p>These include:</p>

            <ul>
                <li>loop interchange, and other unimodular
                transformations.</li>

                <li>loop distribution.</li>

                <li>collapsing tightly nested loops to a single
                loop.</li>

                <li>loop unswitching.</li>
            </ul>

            <p><b>Status:</b>Linear loop transformations are
            implemented by Daniel Berlin.</p>
        </li>

        <li>
            <h3 id="OtherOptimizations">Other Optimizations</h3>

            <ol>
                <li>Exploit data reuse (a la "Compiler-Controlled
                Caching in Superword Register Files for Multimedia
                Extension Architectures" by Shin, Chame and Hall).
                Mostly relies on unroll &amp; jam having been
                applied.</li>

                <li>Vectorize loops that can't be vectorized using
                the classic vectorizer (until the proper loop
                transformations are developed) by applying SLP
                vectorization (a la "Exploiting Superword Level
                Parallelism with Multimedia Instruction Sets" by
                Amarasinghe and Larsen). This scheme can
                potentially more easily vectorize partially
                vectorizable loops, or loops that are already
                unrolled in the source code. It is possible to
                implement SLP vectorization either in the tree
                level or at the RTL level as a complementary
                approach to classic loop vectorization.</li>
            </ol>

            <p><b>Status:</b> Future work.</p>
        </li>

        <li>
            <h3 id="UserHints">User Hints</h3>

            <p> Using user hints for different purposes
                (aliasing, alignment, profitability of vectorizing
                a loop, etc.).</p>

            <p><b>Status:</b> In the works. See <a href=
            "https://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html">
             https://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html</a>.</p>
        </li>
    </ol>
</body>
</html>
